package com.mzy.linear_struct.subject;

/**
 * @Author: codermzy
 * @Date: 2024/04/30/下午12:38
 * @Description:
 */
public class 最大子数组和53 {

    static class Solution {
        public int maxSubArray(int[] nums) {
            if (nums.length < 1) return -1;
            if (nums.length < 2) return nums[0];
            // -2,1,-3,4,-1,2,1,-5,4
            // dp[0]: -2
            // dp[1]: max(nums[1], dp[i-1] + nums[1]) 1
            // dp[2]: -2
            // dp[3]: 4
            // dp[4]: 3
            // dp[5]: 5
            // dp[6]: 6
            // dp[7]: 1
            // dp[8]: 5

            // 1. 定义状态
            int[] dp = new int[nums.length];

            // 2. 确认状态转移方程
            // max(num[i], dp[i-1]+num[i])

            // 3. 初始化状态
            dp[0] = nums[0];

            int answer = dp[0];
            for (int i = 1; i < nums.length; i++) {
                int max = Math.max(nums[i], dp[i - 1] + nums[i]);
                if (max > answer) answer = max;
                dp[i] = max;
            }

            return answer;
        }
    }


    public static void main(String[] args) {

    }
}
